#ifndef _BINARYSEARCHTREE_H_
#define _BINARYSEARCHTREE_H_

#include <iostream>
#include <algorithm>
#include <vector>

template <typename Comparable>
class BinarySearchTree
{
    public:
        /**
         * Construt and initialize a constructor
         */
        BinarySearchTree( ) : root{ nullptr }
            {};

        /**
         * Copy constructor
         */
        BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
        {
            root = clone( rhs.root );
        }

        /**
         * Copy constructor by moving
         */
        BinarySearchTree( BinarySearchTree && rhs )
        {
            root.element = rhs.root.element;
            root.left = rhs.root.left;
            root.right = rhs.root.right;
            delete rhs.root;
        }
        
        /**
         * Destructor for the tree
         */
        ~BinarySearchTree( )
        {
            makeEmpty( );
        }
        
        /**
         * Find the smallest item in a subtree t.
         * 
         */
        const Comparable & finMin() const
        {
            return findMin( root )->element;
        }

        /**
         * Find the largest item in a subtree t.
         * 
         */
        const Comparable & finMax() const
        {
            return findMax( root )->element;
        }

        /**
        * Returns true if x is found in the tree.
        * 
        */
        bool contains( const Comparable & x ) const
        {
            return contains( x, root );
        }

        /**
        * Judge whether the tree is empty.
        * 
        */
        bool isEmpty() const
        {
            return isEmpty( root );
        }

        /**
         * Print the tree contents in sorted order.
         * 
         */
        void printTree() const
        {
            if( isEmpty( ) )
                std::cout << "Empty tree" << std::endl;
            else
                printTree( root );
        }
        
        /**
         * Make subtree empty.
         */
        void makeEmpty()
        {
            makeEmpty( root );
        }

        /**
        * Insert x into the tree; duplicates are ignored.
        * 
        */
        void insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**
        * Insert the type && x into the tree; duplicates are ignored.
        * 
        */
        void insert( Comparable && x )
        {
            insert( x, root );
        }

        /**
        * Remove x from the tree. Nothing is done if x is not found.
        * 
        */
        void remove( const Comparable & x )
        {
            remove( x, root );
        }

        /**
         * Deep copy.
         */
        const BinarySearchTree & operator=( const BinarySearchTree & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }
            return *this;
        }

        /**
         * Deep copy by swaping
         */
        BinarySearchTree & operator=( BinarySearchTree && rhs )
        {
            this.root.element = rhs.root.element;
            this.root.left = rhs.root.left;
            this.root.right = rhs.root.right;
            delete rhs.root;
            return *this;
        }

        /**
         * Insert the elements into the BinarySearchTree so that it is changed increasing.
         */
        void BST_sort( std::vector<Comparable> &_obj )
        {
            if (root != nullptr)
                makeEmpty();
            int num = _obj.size();
            for (int i = 0; i < num; i++)
                insert( _obj[i], root );
        }

        /**
         * Random the elements, then insert the elements into the BinarySearchTree so that it is changed increasing.
         */
        void Randomized_BST_sort( std::vector<Comparable> &_obj )
        {
            if (root != nullptr)
                makeEmpty();
            std::random_shuffle ( _obj.begin(), _obj.end() );
            int num = _obj.size();
            for (int i = 0; i < num; i++)
                insert( _obj[i], root );
        }

        /**
         * Recover the vector by the elements of BinarySearchTree in order.
         */
        void recover( std::vector<Comparable> &_obj)
        {
            recover( _obj, root, 0 );
        }

    private:
        struct BinaryNode
        {
            Comparable element;
            BinaryNode *left;
            BinaryNode *right;

            BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
                : element{ theElement }, left{ lt }, right{ rt } {}

            BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt)
                : element{ std::move( theElement ) }, left{ lt }, right{ rt } {}
        };

        BinaryNode *root;

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void insert( const Comparable & x, BinaryNode * & t )
        {
            if( t == nullptr )
                t = new BinaryNode( x, nullptr, nullptr );
            else if( x < t->element )
                insert( x, t->left );
            else if( t->element < x )
                insert( x, t->right );
            else
                ;  // Duplicate; do nothing
        }

        /**
         * Internal method to insert into a subtree.
         * x is the item to insert by moving.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void insert( Comparable && x, BinaryNode * & t )
        {
            if( t == nullptr)
                t = new BinaryNode{ std::move( x ), nullptr, nullptr};
            else if( x < t->element)
                insert( std::move( x ), t->left );
            else if( t->element < x )
                insert( std::move( x ), t->right );
            else
                ; // Duplicate; do nothing
        }
    
        /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the subtree.
         * Set the new root of the subtree.
         */
        void remove( const Comparable & x, BinaryNode * & t )
        {
            if( t == nullptr )
                return;   // Item not found; do nothing
            if( x < t->element )
                remove( x, t->left );
            else if( t->element < x )
                remove( x, t->right );
            else if( t->left != nullptr && t->right != nullptr ) // Two children
            {
                t->element = findMin( t->right )->element;
                remove( t->element, t->right );
            }
            else
            {
                BinaryNode *oldNode = t;
                t = ( t->left != nullptr ) ? t->left : t->right;
                delete oldNode;
            }
        }

        /**
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        BinaryNode * findMin( BinaryNode *t ) const
        {
            if( t != nullptr )
                while( t->left != nullptr )
                    t = t->left;
            return t;
        }

        /**
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        BinaryNode * findMax( BinaryNode *t ) const
        {
            if( t != nullptr )
                while( t->right != nullptr )
                    t = t->right;
            return t;
        }

        /**
        * Internal method to test if an item is in a subtree.
        *  x is item to search for.
        *  t is the node that roots the subtree.
        * 
        */
        bool contains( const Comparable & x, BinaryNode *t )const
        {
            if( t == nullptr )
                return false;
            else if( x < t->element )
                return contains( x, t->left );
            else if( t->element < x )
                return contains( x, t->right );
            else
                return true;      //Mathch
        }
        
        /**
        * Internal method to judge whether the tree is empty.
        * 
        */
        bool isEmpty( BinaryNode * t ) const
        {
            if( t == nullptr)
                return true;
            else
                return false;
        }

        /**
         * Internal method to make subtree empty.
         */
        void makeEmpty( BinaryNode * & t )
        {
            if( t != nullptr )
            {
                makeEmpty( t->left );
                makeEmpty( t->right );
                delete t;
            }
            t = nullptr;
        }

        /**
         * Internal method to print a subtree rooted at t in sorted order.
         */
        void printTree( BinaryNode *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                std::cout << t->element << " ";
                printTree( t->right );
            }
        }
        
        /**
         * Internal method to clone subtree.
         */
        BinaryNode * clone( BinaryNode *t ) const
        {
            if( t == nullptr )
                return nullptr;
    
            return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
        }

        /**
         * Internal method to recover the vector by the elements of BinarySearchTree in order.
         */
        void recover( std::vector<Comparable> &_obj, BinaryNode * t, int judge )
        {
            if( judge == 0)
                _obj.clear();
            if( t != nullptr)
            {
                recover( _obj, t->left, 1);
                _obj.push_back( t->element );
                recover( _obj, t->right, 1);
            }
        }
};

#else
// Do nothing.
#endif